class ListNode {
    int val;
    ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution10 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // Map<Integer, Integer> map1 = new HashMap<>();
        // Map<Integer, Integer> map2 = new HashMap<>();
        // int index1 = 0, index2 = 0;

        // // 保存每个节点的值到 map 中
        // while (l1 != null) {
        //     map1.put(index1++, l1.val);
        //     l1 = l1.next;
        // }

        // while (l2 != null) {
        //     map2.put(index2++, l2.val);
        //     l2 = l2.next;
        // }

        // // 构建两个数字（注意：这个方法只能处理数字范围不大的情况）
        // int sum1 = 0, sum2 = 0;

        // for (int i = 0; i < index1; i++) {
        //     sum1 += map1.get(i) * Math.pow(10, i);
        // }

        // for (int i = 0; i < index2; i++) {
        //     sum2 += map2.get(i) * Math.pow(10, i);
        // }

        // int totalSum = sum1 + sum2;

        // // 构建结果链表（逆序）
        // ListNode dummy = new ListNode(0);
        // ListNode curr = dummy;

        // if (totalSum == 0) {
        //     return new ListNode(0);
        // }

        // while (totalSum > 0) {
        //     int digit = totalSum % 10;
        //     curr.next = new ListNode(digit);
        //     curr = curr.next;
        //     totalSum /= 10;
        // }

        // return dummy.next;
        //转为数字之后可能会超出数据类型的范围，int，long都接收不了

        ListNode head =null,tail=null;
        int carry=0;
        while(l1!=null||l2!=null){
            int n1= l1!=null?l1.val:0;
            int n2= l2!=null?l2.val:0;
            int sum=n1+n2+carry;
            if(head==null){
                head=tail=new ListNode(sum%10);
            }else{
                tail.next=new ListNode(sum%10);
                tail=tail.next;
            }
            carry=sum/10;
            if(l1!=null){
                l1=l1.next;
            }
            if(l2!=null){
                l2=l2.next;
            }
        }
        //这里需要特殊处理，如果最后进位的话，需要补一个节点
        if(carry>0){
            tail.next=new ListNode(carry);
        }
        return head;


    }

}